from __future__ import print_function
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def printList(l):
	while l:
		print(l.val,end=' ')
		l = l.next
	print()
def creatList(array):
	if array == []:
		return None
	h = ListNode(array[0])
	t = h
	for i in array[1:]:
		t.next = ListNode(i)
		t = t.next
	return h